翻訳と辞書 Words near each other ・ Plouëc-du-Trieux ・ Plouër-sur-Rance ・ Ploučnice ・ Plovan ・ Plovanija ・ Plovdiv ・ Plovdiv Airport ・ PLOT3D file format ・ Ploteus ・ Plothen ・ Ploticus ・ Plotino Rhodakanaty ・ Plotinus ・ Plotius Tucca ・ Plotkin ・ Plotkin bound ・ Plotly ・ Plotnikov ・ Plotopteridae ・ Plotosaurus ・ Plotosus ・ Plotosus canius ・ Plotosus lineatus ・ Plots with a View ・ Plott Balsams ・ Plott Hound ・ Plottage ・ Plotter ・ Plotter (disambiguation) ・ Plotter (instrument) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Plotkin bound ： ウィキペディア英語版 Plotkin bound In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length ''n'' and given minimum distance ''d''. == Statement of the bound == A code is considered "binary" if the codewords use symbols from the binary alphabet $\backslash$. In particular, if all codewords have a fixed length ''n'', then the binary code has length ''n''. Equivalently, in this case the codewords can be considered elements of vector space $\backslash mathbb\_2^n$ over the finite field $\backslash mathbb\_2$. Let $d$ be the minimum distance of $C$, i.e. :$d\; =\; \backslash min\_\; d(x,y)$ where $d(x,y)$ is the Hamming distance between $x$ and $y$. The expression $A\_(n,d)$ represents the maximum number of possible codewords in a binary code of length $n$ and minimum distance $d$. The Plotkin bound places a limit on this expression. Theorem (Plotkin bound): i) If $d$ is even and $2d\; >\; n$, then :$A\_(n,d)\; \backslash leq\; 2\; \backslash left\backslash lfloor\backslash frac\backslash right\backslash rfloor.$ ii) If $d$ is odd and $2d+1\; >\; n$, then :$A\_(n,d)\; \backslash leq\; 2\; \backslash left\backslash lfloor\backslash frac\backslash right\backslash rfloor.$ iii) If $d$ is even, then :$A\_(2d,d)\; \backslash leq\; 4d.$ iv) If $d$ is odd, then :$A\_(2d+1,d)\; \backslash leq\; 4d+4$ where $\backslash left\backslash lfloor\; ~\; \backslash right\backslash rfloor$ denotes the floor function. == Proof of case ''i)''== Let $d(x,y)$ be the Hamming distance of $x$ and $y$, and $M$ be the number of elements in $C$ (thus, $M$ is equal to $A\_(n,d)$). The bound is proved by bounding the quantity $\backslash sum\_\; d(x,y)$ in two different ways. On the one hand, there are $M$ choices for $x$ and for each such choice, there are $M-1$ choices for $y$. Since by definition $d(x,y)\; \backslash geq\; d$ for all $x$ and $y$ ($x\backslash neq\; y$), it follows that :$\backslash sum\_\; d(x,y)\; \backslash geq\; M(M-1)\; d.$ On the other hand, let $A$ be an $M\; \backslash times\; n$ matrix whose rows are the elements of $C$. Let $s\_i$ be the number of zeros contained in the $i$'th column of $A$. This means that the $i$'th column contains $M-s\_i$ ones. Each choice of a zero and a one in the same column contributes exactly $2$ (because $d(x,y)=d(y,x)$) to the sum $\backslash sum\_\; d(x,y)$ and therefore :$\backslash sum\_\; d(x,y)\; =\; \backslash sum\_^n\; 2s\_i\; (M-s\_i).$ If $M$ is even, then the quantity on the right is maximized if and only if $s\_i\; =\; M/2$ holds for all $i$, then :$\backslash sum\_\; d(x,y)\; \backslash leq\; \backslash frac\; n\; M^2.$ Combining the upper and lower bounds for $\backslash sum\_\; d(x,y)$ that we have just derived, :$M(M-1)\; d\; \backslash leq\; \backslash frac\; n\; M^2$ which given that $2d>n$ is equivalent to :$M\; \backslash leq\; \backslash frac.$ Since $M$ is even, it follows that :$M\; \backslash leq\; 2\; \backslash left\backslash lfloor\; \backslash frac\; \backslash right\backslash rfloor.$ On the other hand, if $M$ is odd, then $\backslash sum\_^n\; 2s\_i\; (M-s\_i)$ is maximized when $s\_i\; =\; \backslash frac$ which implies that :$\backslash sum\_\; d(x,y)\; \backslash leq\; \backslash frac\; n\; (M^2-1).$ Combining the upper and lower bounds for $\backslash sum\_\; d(x,y)$, this means that :$M(M-1)\; d\; \backslash leq\; \backslash frac\; n\; (M^2-1)$ or, using that $2d\; >\; n$, :$M\; \backslash leq\; \backslash frac\; -\; 1.$ Since $M$ is an integer, :$M\; \backslash leq\; \backslash left\backslash lfloor\; \backslash frac\; -\; 1\; \backslash right\backslash rfloor\; =\; \backslash left\backslash lfloor\; \backslash frac\; \backslash right\backslash rfloor\; -1\; \backslash leq\; 2\; \backslash left\backslash lfloor\; \backslash frac\; \backslash right\backslash rfloor.$ This completes the proof of the bound. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Plotkin bound」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.